1. Field of the Invention
The present invention relates to an arithmetic apparatus adapted for incorporation in a digital signal processor for performing Viterbi decoding of convolutional codes for error correction.
2. Description of the Related Art
In recent years, the digital signal processor (hereinafter also referred to as DSP in abbreviation) has attracted attention as a processor applicable to portable telephones and the like accompanying an increasing trend of adopting of digital systems in the field of mobile communication services. In a DSP for a speech encoding device for a mobile digital communication system mentioned above, out error correction processing is required in addition to operations such as speech encoding processing. As the error correction procedure, Viterbi decoding maybe adopted.
The Viterbi algorithm is the maximal likelihood decoding of convolutional codes through repetition of simple arithmetic processings such as addition, comparison and selection. In Viterbi decoding, every time the data to be decoded (received data) corresponding to one information bit is obtained, a cumulative number of paths remaining alive (hereinafter also referred to as the pathmetric) in the individual states at that time point is calculated and updated.
FIG. 2 illustrates a state transition in a convolutional encoder of a constraint length K (where K.gtoreq.2) in which two paths indicating state transitions, respectively, extend to a state S(2m) (where m=0, 1, 2, 3, . . . , 2.sup.K-2 -1) and a state S(2m+1) from each of the immediately preceding states S(m) and S(m+2.sup.K-2) at a given time point. In the figure, A(2m) and B(2m) represent output symbols of the paths reaching the state S(2m) and the Hamming distance from the received data (hereinafter referred to as the branchmetrics). Similarly, C(2m+1) and D(2m+1) represent the branchmetrics of the paths reaching the state S(2m+1). In selection of the path, a table containing previously calculated branchmetrics previously is first referred to adding the branchmetrics mentioned above to the pathmetric values of the individual live paths alive at the immediately preceding time point for arithmetically determining a total sum metric for each path. Subsequently, the pathmetrics of the two paths reaching the state S(2m) are compared, whereby the path having a smaller sum of the Hamming distances is selected with the other being discarded. As is now apparent, in the decoding of the convolutional code according to the Viterbi algorithm, that is, the addition, comparison and selection arithmetics and the storage of the pathmetric (more specifically, the additions of the branchmetric to the pathmetrics for the input up to the immediately preceding time point, comparison of the results of additions, and selection of the optimal path) are performed for 2.sup.K-1 states at a series of sequential time points.
For a better understanding of the invention, a typical arithmetic apparatus known heretofore will be described by reference to a schematic diagram shown in FIG. 1 of the accompany drawings.
In FIG. 1, a reference numeral 101 denotes a memory which stores therein instruction words for a processor, pathmetrics (cumulative amounts) of the paths in the individual states of the Viterbi decoding, a table of branchmetric values which the individual paths assume for the value of the coded data (received data) corresponding to one-bit of information, and the results of selections of the live paths (i.e., paths remaining alive) in each of the states and others. Further, reference numeral 102 denotes a data bus connected to the memory 101 used for data transfer and storing results of arithmetic operations. Reference numeral 103 denotes an arithmetic logic circuit for performing arithmetic logic operations. Reference numerals 104 and 105 denote latch circuits for temporarily storing a right input value and a left input value, respectively, for the arithmetic logic circuit 103. Numerals 106 and 107 denote registers each serving for temporarily storing the result of an operation.
In the arithmetic apparatus having the structure implemented as described above, operations for updating the pathmetric in the state S(2m) shown in FIG. 2 and operation for storing the path select signal through the addition, comparison and selection processes in the Viterbi decoding for one received bit of data will be elucidated below by classifying the processing into six steps (1) to (6).
(1) First addition step of pathmetric and branchmetric
The pathmetric value in the state S(m) shown in FIG. 2 is stored in the latch circuit 104 from the memory 101 via the bus 102, while the value of branchmetric A(2m) is similarly stored in the latch circuit 105 from the memory 101 via the bus 102. The arithmetic logic circuit 103 performs addition of the contents of the latch circuits 104 and 105, the result of which is stored in the register 106. PA1 The value of pathmetric in the state S(m+2.sup.K-2) shown in FIG. 2 is stored in the latch circuit 104 from the memory 101 via the bus 102, while the value of the branchmetric B(2m) is stored in the latch circuit 105 from the memory 101 via the bus 102. The arithmetic logic circuit 103 adds the contents of the latch circuits 104 and 105, the result of which is stored in the register 107. PA1 The contents of the registers 106 and 107 are transferred to the latch circuits 104 and 105, respectively. The arithmetic logic circuit 103 performs subtraction between the contents of the latch circuits 104 and 105. However, the result of this subtraction is not stored. PA1 A controller (not shown) determines the sign of the result of the substraction performed in the step (3) to thereby effect a program control (branching) in a step (5) or (6) mentioned below. PA1 When the decision step 4) shows that the result of the subtraction in the step (3) is minus, that is, negative, the content of the register 106 is stored in memory 101. Otherwise, the content of the register 107 is stored in memory 101. PA1 When the decision step (4) shows that the result of the subtraction step (3) is minus or negative, a value of "0" is stored in the memory 101. Otherwise, a value of "1" is stored in the memory 101.
(2) Second addition step of pathmetric and branchmetric
(3) Subtraction (comparison) step of results of the two addition steps
(4) Sign decision (selection) step of results of the substraction
(5) Step of storing the addition result decided as being smaller (updating of the pathmetric)
(6) Step of storing a path select signal
By repeating the six steps (1) to (6) mentioned above 2.sup.K-1 times, the pathmetrics for all the states are updated.
As is now apparent from the above, in the arithmetic apparatus known heretofore, the Viterbi decoding processing can be realized through the addition and the comparison performed by the arithmetic logic circuit 103 and by controlling the programs in dependence on the result of the comparison.
The arithmetic apparatus known heretofore suffers from problems in that a large number of operation steps are involved for a single routine of the addition, comparison and the selection arithmetics and that a large memory capacity is required because the single-bit path select signal is stored in one word of the memory.